package qjc.d_子串;

import java.util.ArrayDeque;
import java.util.Deque;

public class b_滑动窗口最大值 {
    /**
     * 定义一个泛型单调队列类，在尾部加入元素，保持单调递减，从头部删除元素，只有等于队头才删，
     * 获取当前窗口的最大值（队头元素），遍历数组，如果当前窗口已经包含 k 个元素，
     * 移除窗口最左边的元素，将当前元素加入单调队列，如果当前窗口已经包含 k 个元素，
     * 记录当前窗口的最大值
     */
    public class MonotionQueue<T extends Comparable<T>>{
        private final Deque<T> deque = new ArrayDeque<>();
        public void push(T t){
            while (!deque.isEmpty() && deque.peekLast().compareTo(t) < 0){
                deque.removeLast();
            }
            deque.addLast(t);
        }

        public void pop(T t){
            if(!deque.isEmpty() && deque.peekFirst().equals(t)){
                deque.removeFirst();
            }
        }

        public T peek(){
            return deque.peekFirst();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotionQueue<Integer> q = new MonotionQueue<>();
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if(i >= k && nums[i - k] == q.peek()){
                q.pop(nums[i - k]);
            }
            int num = nums[i];
            q.push(num);
            if(i >= k - 1){
                res[i - k + 1] = q.peek();
            }
        }
        return res;
    }
}
